Juego de Evitador-Forzador
Un juego Evitador-Forzador[1] (también llamado juego Anticreador-Antirompedor[2][3]) es una especie de juego posicional. Como la mayoría de los juegos posicionales, se describe mediante un conjunto de posiciones / puntos / elementos () y una familia de subconjuntos (), que se denominan aquí los conjuntos perdedores. Es jugado por dos jugadores, llamados Evitador y Forzador, que se turnan para elegir elementos hasta que se toman todos los elementos. El evitador gana si logra evitar llevarse un conjunto perdedor; Forzador gana si logra que Evitador se lleve un conjunto perdedor.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/75/Complete_graph_K6.svg/220px-Complete_graph_K6.svg.png)
Un ejemplo clásico de tal juego es Sim. Allí, las posiciones son todos los bordes del gráfico completo en 6 vértices. Los jugadores se turnan para sombrear una línea de su color y pierden cuando forman un triángulo completo de su propio color: los conjuntos perdedores son todos los triángulos.
Comparación con los juegos Creador-Rompedor
[editar]La condición ganadora de un juego Evitador-Forzador es exactamente lo opuesto a la condición ganadora del juego Creador-Rompedor en el mismo . Por lo tanto, el juego Evitador-Forzador es la variante del juego misère del juego Creador-Rompedor. Sin embargo, existen diferencias contraintuitivas entre estos tipos de juegos.
Por ejemplo, considérese la versión sesgada de los juegos, en la que el primer jugador toma p elementos en cada turno y el segundo jugador toma q elementos en cada turno (en la versión estándar p=1 y q=1). Los juegos Creador-Rompedor son monótonos con prejuicios: tomar más elementos siempre es una ventaja. Formalmente, si Creador gana el juego (p:q) Creador-Rompedor, también gana el juego (p +1: q) y el juego (p:q-1). Los juegos de Evitador-Forzador no son monótonos: tomar más elementos no siempre es una desventaja. Por ejemplo, considérese un juego de Evitador-Forzador muy simple donde los conjuntos perdedores son {w, x} e {y, z}. Entonces, Evitador gana el juego (1:1), Forzador gana el juego (1:2) y Evitador gana el juego (2:2).
Existe una variante monótona de las (p:q) reglas del juego Evitador-Forzador, en la que el Evitador tiene que elegir al menos p elementos en cada turno y Forzador tiene que elegir al menos q elementos en cada turno; esta variante es sesgada-monótona.[1]
Evasión parcial
[editar]De manera similar a los juegos Creador-Rompedor, los juegos Evitador-Forzador también tienen generalizaciones fraccionarias.
Suponga que el Evitador necesita evitar tomar al menos una fracción t de los elementos en cualquier conjunto ganador (es decir, tomar como máximo 1 t de los elementos en cualquier conjunto), y Forzador necesita evitar esto, es decir, Forzador necesita tomar menos que una fracción t de los elementos en algún conjunto ganador. Defina la constante (en la variante estándar, ).
- Si, y el número total de elementos es par, Evitador tiene una estrategia ganadora cuando juega primero.[3]
Referencias
[editar]- ↑ a b Hefetz, Dan; Krivelevich, Michael; Stojakovic, Milos; Szabó, Tibor (3 de julio de 2014). Positional Games (en inglés). Springer Basel. ISBN 978-3-0348-0824-8. Consultado el 15 de febrero de 2021.
- ↑ «ISSN 1077-8926 (Online) | The Electronic journal of combinatorics | The ISSN Portal». portal.issn.org. Consultado el 15 de febrero de 2021.
- ↑ a b Lu, Xiaoyun (29 de noviembre de 1991). «A matching game». Discrete Mathematics (en inglés) 94 (3): 199-207. ISSN 0012-365X. doi:10.1016/0012-365X(91)90025-W.